package com.fanshuai.skiplist;

import java.util.Random;

public class SkipList<V> implements ISkipList<V> {
    public static class SkipListNode<V> {
        public double key;
        public V value;

        public SkipListNode<V> left;
        public SkipListNode<V> right;
        public SkipListNode<V> up;
        public SkipListNode<V> down;

        public SkipListNode(double key, V v) {
            this.key = key;
            this.value = v;
        }
    }

    private SkipListNode<V> tail, head;  //头结点  尾结点  位于最上层链表。当链表向上提升时，头结点和尾结点向上转移
    private int nodes;  //底层数据节点总数
    private int listlevel;  //链表层数

    private static int MAX_LEVEL = 64; //最大层数

    private Random random;  //生成随机数，决定是否向上提升
    private static final double probability = 0.5; //链表向上提升的概率

    public SkipList() {
        tail = new SkipListNode<>(Double.MAX_VALUE, null);
        head = new SkipListNode<>(Double.MIN_VALUE, null);
        horizontalLink(head, tail);

        nodes = 0;
        listlevel = 1;

        random = new Random(System.currentTimeMillis());
    }

    /**
     * 发现小于等于当前key的底层链表node
     * @param key
     * @return
     */
    private SkipListNode<V> findNode(double key) {
        SkipListNode<V> node = head;
        while (true) {
            while (Double.compare(node.right.key, key) <= 0) {
                node = node.right;
            }
            if (node.down != null) {
                node = node.down;
            } else {
                break;
            }
        }

        return node;
    }

    @Override
    public void add(double key, V value) {
        SkipListNode<V> node = findNode(key);
        if (Double.compare(node.key, key) == 0) {
            node.value = value;
            return;
        }

        SkipListNode<V> q = new SkipListNode<>(key, value);
        backLink(node, q);

        int currentLevel = 1;
        //抛硬币，提升上层链表
        while (listlevel < MAX_LEVEL && random.nextDouble() >= probability) {
            if (currentLevel >= listlevel) {
                SkipListNode<V> p1 = new SkipListNode<>(Double.MIN_VALUE, null);
                SkipListNode<V> p2 = new SkipListNode<>(Double.MAX_VALUE, null);

                horizontalLink(p1, p2);
                vervicalLink(p1, head);
                vervicalLink(p2, tail);

                head = p1;
                tail = p2;
                listlevel++;
            }
            currentLevel++;

            while (node.up == null) {
                node = node.left;
            }
            node = node.up;

            //上层链表只存储key，不存value
            SkipListNode<V> newQ = new SkipListNode<>(key, null);
            backLink(node, newQ);

            vervicalLink(newQ, q);
            q = newQ;
        }

        nodes++;
    }

    /**
     * 最长层链表收尾连接
     * @param p
     * @param q
     */
    private void backLink(SkipListNode<V> p, SkipListNode<V> q) {
        SkipListNode<V> next = p.right;
        q.right = next;
        next.left = q;
        q.left = p;
        p.right = q;
    }

    /**
     * q插入p之后
     * @param p
     * @param q
     */
    private void horizontalLink(SkipListNode<V> p, SkipListNode<V> q) {
        p.right = q;
        q.left = p;
    }

    /**
     * 上下层节点连接
     * @param p
     * @param q
     */
    private void vervicalLink(SkipListNode<V> p, SkipListNode<V> q) {
        p.down = q;
        q.up = p;
    }

    /**
     * 从head开始搜索最上层链表，找到最底层<=key的节点，判断key是否相等
     * @param key
     * @return
     */
    @Override
    public V search(double key) {
        SkipListNode<V> node = findNode(key);
        if (Double.compare(node.key, key) == 0) {
            return node.value;
        }

        return null;
    }

    @Override
    public boolean isEmpty() {
        return nodes == 0;
    }

    @Override
    public int size() {
        return nodes;
    }
}
